package 无重叠区间;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: AirMan
 * @date: 2025/4/25 19:10
 * @description:
 */
public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // greedy
        // 首先对区间进行排序，排序的依据就是区间的左边界大小
        // 这道题和《用最少数量的箭引爆气球》类似，只不过这道题是要寻找“非交叉区间的最大数量”
        // 最少移除数 = 总区间数 - 非交叉区间的最大数
        // 如何寻找非交叉区间的最大数？一直记录前面区间的右区间的最小值，只要出现当前区间的左边界 >= 前面区间有边界的最小值
        // 那么我们就找到当前局部情况的非交叉区间的最大值，同时更新当前的最小右区减数(后续重新找基准)
        // 局部最优：当区间没有重叠时，去除重叠部分就得到了最多的非重叠区间

        Arrays.sort(intervals, (Comparator.comparingInt(o -> o[0])));
        int intersectionZone = 1;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i - 1][1] <= intervals[i][0]) {
                intersectionZone++;
            } else {
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return intervals.length - intersectionZone;
    }
}
